package main

import "fmt"

var solutions [][]int

func isSafe(board []int, row, col int) bool {
    for i := 0; i < row; i++ {
        if board[i] == col {
            return false
        }
        if abs(row-i) == abs(col-board[i]) {
            return false
        }
    }
    return true
}

func abs(n int) int {
    if n < 0 {
        return -n
    }
    return n
}

func solveNQueens(n int) [][]int {
    solutions = nil
    board := make([]int, n)
    backtrack(0, n, board)
    return solutions
}

func backtrack(row, n int, board []int) {
    if row == n {
        newBoard := make([]int, n)
        copy(newBoard, board)
        solutions = append(solutions, newBoard)
        return
    }
    for col := 0; col < n; col++ {
        if isSafe(board, row, col) {
            board[row] = col
            backtrack(row+1, n, board)
        }
    }
}

func main() {
    solutions := solveNQueens(8)
    for _, solution := range solutions {
        for _, col := range solution {
            for i := 0; i < 8; i++ {
                if i == col {
                    fmt.Print("Q ")
                } else {
                    fmt.Print(". ")
                }
            }
            fmt.Println()
        }
        fmt.Println()
    }
}
